package uestc.lj.basic.listnode;

import java.util.HashMap;

/**
 * 复制含有随机指针节点的链表
 *
 * @Author:Crazlee
 * @Date:2021/11/22
 */
public class Code05_CopyListWithRandom {
	public static class Node {
		public int value;
		public Node next;
		public Node rand;

		public Node(int data) {
			this.value = data;
		}
	}


	public static Node copyListWithRandUsingExtraSpaces(Node head) {
		HashMap<Node, Node> map = new HashMap<>();
		Node cur = head;
		while (cur != null) {
			map.put(cur, new Node(cur.value));
			cur = cur.next;
		}
		cur = head;
		while (cur != null) {
			map.get(cur).next = map.get(cur.next);
			map.get(cur).rand = map.get(cur.rand);
			cur = cur.next;
		}
		return map.get(head);
	}

	public static Node copyListWithRand(Node head) {
		if (head == null) {
			return null;
		}
		Node cur = head;
		Node next = null;
		//创建克隆节点，使其连接在原节点之后
		while (cur != null) {
			next = cur.next;
			cur.next = new Node(cur.value);
			cur.next.next = next;
			cur = next;
		}
		cur = head;
		Node curCopy = null;
		//修改克隆节点的rand指针
		while (cur != null) {
			next = cur.next.next;
			curCopy = cur.next;
			curCopy.rand = cur.rand != null ? cur.rand.next : null;
			cur = next;
		}
		Node res = head.next;
		cur = head;
		//分离原节点和克隆节点
		while (cur != null) {
			next = cur.next.next;
			curCopy = cur.next;
			cur.next = next;
			curCopy.next = next != null ? next.next : null;
			cur = next;
		}
		return res;
	}
}
